package leetcode.editor.cn;
//给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 
//
// 你需要返回给定数组中的重要翻转对的数量。 
//
// 示例 1: 
//
// 
//输入: [1,3,2,3,1]
//输出: 2
// 
//
// 示例 2: 
//
// 
//输入: [2,4,3,5,1]
//输出: 3
// 
//
// 注意: 
//
// 
// 给定数组的长度不会超过50000。 
// 输入数组中的所有数字都在32位整数的表示范围内。 
// 
// Related Topics 树状数组 线段树 数组 二分查找 分治 有序集合 归并排序 
// 👍 409 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution90 {
    public int reversePairs(int[] nums) {
        temp = new int[nums.length];
        sort(nums, 0, nums.length - 1);
        return count;
    }


    // 记录「翻转对」的个数
    int count = 0;
    private int[] temp;

    private void sort(int[] nums, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = low + (high - low) / 2;
        sort(nums, low, mid);
        sort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }

    private void merge(int[] nums, int low, int mid, int high) {
        System.arraycopy(nums, low, temp, low, high - low + 1);
//
//        // 在合并有序数组之前，加点私货
//        for (int i = low; i <= mid; i++) {
//            // 对于左半边的每个 nums[i]，都去右半边寻找符合条件的元素
//            for (int j = mid + 1; j <= high; j++) {
//                // nums 中的元素可能较大，乘 2 可能溢出，所以转化成 long
//                if ((long) nums[i] > (long) nums[j] * 2) {
//                    count++;
//                }
//            }
//        }


        // 进行效率优化，维护左闭右开区间 [mid+1, end) 中的元素乘 2 小于 nums[i]
        // 为什么 end 是开区间？因为这样的话可以保证初始区间 [mid+1, mid+1) 是一个空区间
        int end = mid + 1;
        for (int i = low; i <= mid; i++) {
            // nums 中的元素可能较大，乘 2 可能溢出，所以转化成 long
            while (end <= high && (long) nums[i] > (long) nums[end] * 2) {
                end++;
            }
            count += end - (mid + 1);
        }

        if (temp[mid] > temp[mid + 1]) {
            int l = low;
            int m = mid + 1;

            for (int p = low; p <= high; p++) {
                if (l == mid + 1) {
                    // 左半边数组已全部被合并
                    nums[p] = temp[m++];
                } else if (m == high + 1) {
                    // 右半边数组已全部被合并
                    nums[p] = temp[l++];
                } else if (temp[l] > temp[m]) {
                    nums[p] = temp[m++];
                } else if (temp[l] <= temp[m]) {
                    nums[p] = temp[l++];
                }
            }
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)
